package demo3;

import java.util.*;

class Item {
    int weight;
    int value;
    double valuePerWeight;
    
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.valuePerWeight = (double)value / weight;
    }
}

public class KnapsackGreedy {
    public static void solveKnapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        Item[] items = new Item[n];
        
        // 创建物品数组
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i]);
        }
        
        // 按单位重量价值降序排序
        Arrays.sort(items, (a, b) -> Double.compare(b.valuePerWeight, a.valuePerWeight));
        
        double sum = 0;
        int remainingCapacity = capacity;
        double[] fractions = new double[n];
        
        // 贪心
        for (int i = 0; i < n; i++) {
            if (remainingCapacity >= items[i].weight) {
                fractions[i] = 1.0;
                sum += items[i].value;
                remainingCapacity -= items[i].weight;
            } else {
                fractions[i] = (double)remainingCapacity / items[i].weight;
                sum += items[i].value * fractions[i];
                break;
            }
        }
        

        System.out.println("背包问题解决方案：");
        System.out.println("物品\t重量\t价值\t装入比例");
        for (int i = 0; i < n; i++) {
            if (fractions[i] > 0) {
                System.out.printf("%d\t%d\t%d\t%.2f%n", 
                    i+1, items[i].weight, items[i].value, fractions[i]);
            }
        }
        System.out.printf("总价值: %.2f%n", sum);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.print("请输入物品数量: ");
        int n = scanner.nextInt();
        
        int[] weights = new int[n];
        int[] values = new int[n];
        
        System.out.println("请依次输入每个物品的重量:");
        for (int i = 0; i < n; i++) {
            weights[i] = scanner.nextInt();
        }
        
        System.out.println("请依次输入每个物品的价值:");
        for (int i = 0; i < n; i++) {
            values[i] = scanner.nextInt();
        }
        
        System.out.print("请输入背包容量: ");
        int capacity = scanner.nextInt();
        
        solveKnapsack(weights, values, capacity);
        scanner.close();
    }
}